#include <vector>
using namespace std;
class Solution
{
    bool row[9][9];
    bool col[9][9];
    bool block[3][3][9];
    vector<pair<int, int>> location;

public:
    void solveSudoku(vector<vector<char>> &board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.')
                {
                    location.emplace_back(i, j);
                }
                else
                {
                    row[i][board[i][j] - '1'] = true;
                    col[j][board[i][j] - '1'] = true;
                    block[i / 3][j / 3][board[i][j] - '1'] = true;
                }
            }
        }
        solve(board,0);
    }
    bool solve(vector<vector<char>> &board, int pos)
    {
        if (pos == location.size())
        {
            return true;
        }
        int x, y;
        x = location[pos].first;
        y = location[pos].second;
        for (int i = 0; i < 9; i++)
        {
            if (row[x][i] || col[y][i] || block[x / 3][y / 3][i])
            {
                continue;
            }
            row[x][i] = true;
            col[y][i] = true;
            block[x / 3][y / 3][i] = true;
            board[x][y] = i + '1';
            bool ans = solve(board, pos + 1);
            if (ans)
            {
                return true;
            }
            row[x][i] = false;
            col[y][i] = false;
            block[x / 3][y / 3][i] = false;
        }
        return false;
    }
};
int main(int argc, char const *argv[])
{

    return 0;
}
